package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;
import cn.pugle.oj.catalog.LinkedProblem;
import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * 优化一下, 8 ms
 *
 * // 艹, 这根本不叫并查集
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC128_1 implements GraphProblem, TreeProblem {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        HashMap<Integer, Boolean> unionFind = new HashMap<>();//boolean表示是否有next数
        for (int num : nums) {
            int pre = num - 1, next = num + 1;
            if (unionFind.containsKey(pre)) unionFind.put(pre, true);
            if (unionFind.containsKey(next)) {
                unionFind.put(num, true);
            } else {
                unionFind.put(num, false);
            }
        }//On时间 On空间

        int longest = 0;
        HashMap<Integer, Integer> cache = new HashMap<>();
        for (Integer key : new ArrayList<>(unionFind.keySet())) {
            int cur = key;
            while (unionFind.containsKey(cur) && unionFind.get(cur)) {
                unionFind.remove(cur);
                cur = cur + 1;
            }
            if (cache.containsKey(cur)) {
                cur += cache.get(cur);
            }
            longest = Math.max(longest, cur - key);
            cache.put(key, cur - key);
        }
        return longest + 1;
    }

    public static void main(String[] args) {
        System.out.println(new LC128_1().longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
        System.out.println(new LC128_1().longestConsecutive(new int[]{100, 4, 101, 1, 102, 3, 9}));
    }
}
